Distance transformations are used to compute the distance between a point to an object. In image processing, for example, a distance transform may be used to compute the distance from an individual point of the image to a set of source feature points or a boundary curve in the image. The boundary curve(s) may be provided in a continuous parametric form. A continuous distance map represents the distance transform for every point in the continuous image plane. For practical applications, the distance transform values are calculated only at discrete grid locations that constitute a sampling of the continuous distance map. The resulting distance map image describes the distance between each of the grid points and a set of source feature points or boundary curves in the image which in principle are not constrained to be on the same sampling grid.
Distance maps are useful in pattern recognition and pattern matching. For example, distance maps may be used to locate an object within an image or for optical character recognition. Other applications include medical imaging (e.g., registration for 3D medical images) and generating structural “skeletons” of an object.
A number of metrics may be used by the distance transform. For example the “city block” approach measures the length (L1) of the path taken in pixel increments to the boundary curve. The city block approach is based on the L1 norm such that the arclength is defined as ds=|dx|+|dy|. The city block approach tends to preserve errors when the grid resolution is refined. The Euclidean approach is based on the L2 norm such that the arclength is defined as ds=√{square root over (dx2+dy2)}. Other distance transforms include the chess board, chamfer, and squared Euclidean metric.
Several methods for performing distance map calculations assume that feature points reside at the locations of the same sampling grid as the distance map (regardless of the selected distance metric). The discrete nature of the feature point location is ignored when computing the path distance so that allowable distance values can be real numbers (e.g., distance values are square roots of non-negative integers under the Euclidean metric).
Although these distance values can be calculated with great precision (corresponding to many decimal digits), the possible distance values are still a discrete set and thus have limited accuracy. As a result, the distance value may not accurately reflect the location of the boundary curve, especially at small distances of the order of the grid separation from the boundary curve. Accordingly, any distance transform method that relies on the assumption that feature points lie exactly on grid points may be inappropriate when the source feature points or boundary curves lie between grid points or pixels. Methods for computing distance maps relative to feature points on the same grid have a relatively low computational complexity O(N), where N is the number of pixels in the source image and the calculated distance map (e.g., the Danielsson four scan approach).
Alternative methods have been proposed for calculating distance maps on a grid of pixels where the boundary curve location is defined to sub-pixel accuracy (i.e., not restricted to the grid). These techniques typically propagate the “wave front” of the distance information using heap-sort operations. Thus although the resulting distance maps are potentially more accurate than techniques that limit boundary curves to grid points, one disadvantage of typical approaches to computing distance maps with sub-pixel boundary curve locations is that the computational complexity tends to increase to O(NlogN).